#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 剑指 Offer 54. 二叉搜索树的第k大节点.py
@time: 2022/3/4 12:00
@desc: https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/
> 给定一棵二叉搜索树，请找出其中第 k 大的节点的值。
示例 1:
输入: root = [3,1,4,null,2], k = 1
       3
      / \
     1   4
      \
       2
输出: 4

1. DFS, 配合剪枝, Ot(N), Os(N),栈空间
'''
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x, left=None, right=None):
        self.val = x
        self.left = left
        self.right = right

class Solution:
    def kthLargest(self, root: TreeNode, k: int) -> int:
        if not root: return None
        def dfs(root):
            if not root: return
            dfs(root.right)
            self.count += 1
            if self.count==k:
                self.ans = root.val
                return
            # 剪枝
            if self.count<=k: dfs(root.left)
        self.count = 0
        self.ans = None
        dfs(root)
        return self.ans

if __name__ == '__main__':
    root = TreeNode(3, left=TreeNode(1, right=TreeNode(2)), right=TreeNode(4))
    Solution().kthLargest(root, 1)